The present invention relates to seek operations and rotating disc drive memory assemblies. More particularly, the present invention relates to a method for sorting the command queue to reduce rotational latency in disc drive memory assemblies.
Rotating disc memories include one or more discs driven about a spindle axis. Each disc has a plurality of concentric tracks, on one or both surfaces from which information is read or onto which information is written by a read/write element. In addition, each track is further divided into a plurality of sectors. A track cylinder is formed by the radially corresponding tracks on the disc memories. In a disc drive system, a disc rotates at a high speed while the read/write element "flies" over the surface of the rotating disc. The read/write element is positioned over specific areas or sectors of the disc in accordance with commands received from the host computer.
The SCSI interface protocol provides a mechanism for host computers to send multiple commands to a disc drive. It allows the disc drive to determine the optimum order of execution for the commands. The set of commands available for execution by the disc drive is referred to as the "command queue".
Traditionally, disc drives have sorted the command queue in an order that minimizes seek time between the various commands. The seek time is the time required for the read/write element to radially move across or traverse cylinders between the present cylinder over which the read/write element is positioned and the cylinder to be addressed by the particular command.
However, seek time is only one of two components of the true access time of a command. The other component is the rotational latency time or the amount of time the disc drive spends waiting for the appropriate data to rotate under the read/write element. The rotational latency time is a significant part of the total access time for all but the longest seeks. On average, it is the dominant component of the total access time for relatively short seeks.
To determine the optimum order of execution of a set of commands, it is desirable to consider the full access time between commands rather than simply the seek time. An ideal sorting or disc scheduling algorithm would sort the command queue in such a way that the sum of the access times of all of the commands in the queue is minimized. This would involve computing the sum of the access times for each of the possible orders of the queue. Computing access times for every possible order, however, is far too computationally intensive to do in a real-time system such as a disc drive. For example, there are over three million possible orders in a set of ten commands. Modern disc drives can have up to 64 or more commands in the command queue. In addition, the command queue in practical applications is dynamic. In other words, new commands are constantly received from the host computer. Thus, the optimum order of execution of previously received commands often changes, requiring the entire queue to be re-sorted.
Since the above-mentioned ideal algorithm is impractical, alternative methods of disc scheduling have been devised. One such disc scheduling algorithm is the shortest access time first algorithm discussed in Jacobson et al., "Disc Scheduling Algorithm Based On Rotational Positions", Hewlett-Packard Laboratories Technical Report, HPL-CSP-91-7, Feb. 26, 1991, pp. 5-18. The shortest access time first algorithm scans the command queue of pending commands and calculates an access time for each command given the known position of the read/write element (if the disc is idle), or the expected position of the read/write element at the end of the current command. The access time is calculated by using a static array containing seek times for each possible seek distance. To reduce the number of commands which must be scanned and for which an access time must be calculated, the shortest access time first algorithm divides the disc into a number of bins. The commands in the command queue are grouped based on the location addressed by each particular command. The bins are then searched in an order determined by a current position of read/write element. The order of bins to be searched based upon the current location of the read/write element is precomputed and stored in an array indexed by the position of the read/write element. The list of bin orderings may require about eight kilobytes of memory for a disc divided into 64 bins.
To select a command for execution, the algorithm calculates an access time for each of the commands grouped into the first non-empty bin found. After the access time for each of the commands is calculated, the command having the shortest access time is generally executed. However, some bins contain cylinders on both sides of the rotational latency line or head trajectory. In other words, some bins may contain only command addresses that can only be accessed in two revolutions. To cope with scenarios where the first non-empty bin contains only command addresses outside of the rotational latency line or head trajectory, the algorithm additionally requires that a threshold value be calculated and stored for each bin or cell. The threshold value represents the largest possible access time a command may have to be executed. After an access time is calculated for each and every command location within the particular bin being scanned, the best or smallest access time of all the commands is compared with the threshold value. If the best access time of all the commands is below the threshold value, the command having the lowest access time is executed. However, if the best access time of all the command addresses within the bin is greater than the threshold value, the algorithm repeats by scanning all of the commands and calculating an access time for all of the commands in the next non-empty bin.
Although the shortest access time first scheduling algorithm is an improvement over sorting algorithms which merely minimize seek time between commands, the shortest access time first algorithm has several drawbacks. First, the shortest access time first method is extremely time consuming for commands which address clustered locations on the disc. In the operation of many systems, the command queue may, at any one moment, contain a set of commands which address locations that are clustered in a particular area of the disc. As a result, a single bin may contain an extremely large number of command addresses. Because the shortest access time first algorithm requires that the access time be calculated for each and every command address within the particular bin, the algorithm is extremely time consuming for a bin containing clustered addresses for a large number of commands.
Second, the shortest access time first algorithm requires a significant amount of memory. As discussed above, the shortest access time first algorithm requires an array indexed by a position of the read/write element which lists a bin search order for each possible starting bin. In addition, the algorithm further requires an array containing threshold values for each bin. The eight kilobytes of memory required for the array is significant compared to the amount of memory available on some disc drives.